package org.activequant.math.algorithms;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;

/**
 * Generic close-open interval set. The set is always normalized, meaning that
 * there are no intersecting or mergeable intervals there.
 * <br/>
 * IntervalSet&lt;T extends Comparable&lt;T&gt;&gt; implements Iterable&lt;Interval&lt;T&gt;&gt;. Holds the following associated variables:
 * <ul>
 * <li>list(List&lt;Interval&lt;T&gt;&gt;)</li>
 * <li>headComparator(Comparator&lt;Interval&lt;T&gt;&gt;)</li>
 * </ul>
 * <b>History:</b><br>
 *  - [05.11.2007] Created (Mike Kroutikov)<br>
 *
 *  @author Mike Kroutikov
 */
public class IntervalSet<T extends Comparable<T>> implements Iterable<Interval<T>> {
	/**
	 * private final List&lt;Interval&lt;T&gt;&gt; list = new ArrayList&lt;Interval&lt;T&gt;&gt;();
	 */
	private final List<Interval<T>> list = new ArrayList<Interval<T>>();
	/**
	 * private final Comparator&lt;Interval&lt;T&gt;&gt; headComparator = new Comparator&lt;Interval&lt;T&gt;&gt;() {...}<br/>
	 * An Interval Comparator whose <code>compare(Interval&lt;T&gt; o1, Interval&lt;T&gt; o2)</code> method compares o1.to and o2.from
	 */
	private final Comparator<Interval<T>> headComparator = new Comparator<Interval<T>>() {
		public int compare(Interval<T> o1, Interval<T> o2) {
			return o1.to.compareTo(o2.from);
		}
	};

	/**
	 * Merges interval into the current set. This is analogous to <code>add()</code>
	 * operation, but takes care of necessary interval merging that guarantees that
	 * the result is normalized.<br/>
	 * Through binary search it finds the proper position for the given arg(Interval&lt;T&gt;) within the (sorted) associated list(List&lt;Interval&lt;T&gt;&gt;).<br/>
	 * Checks whether the given Interval can be merged with the Interval at that position, and if possible merges them. Otherwise it just inserts the given arg(Interval&lt;T&gt;)
	 * at that position into the associated list(List&lt;Interval&lt;T&gt;&gt;) and shifts succeeding Intervals to the right.
	 * @param arg interval to merge in.
	 */
	public void mergeIn(Interval<T> arg) {
		
		int index = Collections.binarySearch(list, arg, headComparator);
		if(index < 0) {
			index = - (index + 1);
		}
		
		while(index < list.size()) {
			Interval<T> curr = list.get(index);
			if(arg.isMergeableWith(curr)) {
				arg = arg.mergeWith(list.remove(index));
			} else {
				break;
			}
		}
		list.add(index, arg);
	}
	
	/**
	 * Intersects this set with the given interval and returns the result of
	 * intersection. Current set is not changed.<br/>
	 * returns an IntervalSet&lt;T&gt; whose list(List&lt;Interval&lt;T&gt;&gt;) holds any intersections of the given arg(Interval&lt;T&gt;) with the associated list(List&lt;Interval&lt;T&gt;&gt;).
	 * @param arg interval to intersect with.
	 * @return intersection set (may be empty).
	 */
	public IntervalSet<T> intersect(Interval<T> arg) {

		int index = Collections.binarySearch(list, arg, headComparator);
		if(index < 0) {
			index = - (index + 1);
		}
		
		IntervalSet<T> out = new IntervalSet<T>();
		while(index < list.size()) {
			Interval<T> curr = list.get(index);
			if(arg.isIntersectableWith(curr)) {
				out.list.add(arg.intersectWith(curr));
				index++;
			} else {
				break;
			}
		}
		
		return out;
	}
	/**
	 * returns an Iterator&lt;Interval&lt;T&gt;&gt; for the associated list(List&lt;Interval&lt;T&gt;&gt;)
	 */
	public Iterator<Interval<T>> iterator() {
		return list.iterator();
	}
	/**
	 * returns a String representation of the associated list(List&lt;Interval&lt;T&gt;&gt;)
	 */
	public String toString() {
		return list.toString();
	}
}
